#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<string> path={"JFK"};
    unordered_map<string, map<string,int>> targets;
    bool flag_find = false;
    void dfs(int k, int n, map<string,int> &nxt_targets){
        if(k == n) {flag_find=true; return;}
        for(auto& iter: nxt_targets){
            if(iter.second <=0) continue;
            --iter.second;  path.emplace_back(iter.first);
            dfs(k+1, n, targets[iter.first]);
            if(flag_find == true) break;
            ++iter.second;  path.pop_back();
        }
    }
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        for(auto& ticket: tickets){
            targets[ticket[0]][ticket[1]]++;
        }
        dfs(0, tickets.size(), targets[path.back()]);
        return path;
    }
};

int main(){
    Solution solution;
    vector<vector<string>> tickets = {{"JFK","SFO"},{"JFK","ATL"},{"SFO","ATL"},{"ATL","JFK"},{"ATL","SFO"}};
    solution.findItinerary(tickets);
}